Phụ Công Thạch là người Tề châu (齊州, nay gần tương ứng với Tế Nam, Sơn Đông). Ông thường trộm cừu của thúc phụ mình để trao cho bằng hữu thân thiết nhất là Đỗ Phục Uy, khiến cả hai bị quan phủ chú ý đến. Họ chạy trốn và trở thành các thủ lĩnh nổi dậy chống lại triều Tùy vào năm 613 hoặc trước đó. Đỗ Phục Uy sau đó trở thành một thủ lĩnh nổi dậy lớn mạnh, tự xưng là tổng quản, Phụ Công Thạch được trao chức trưởng sử. Năm 613, theo lệnh của Đỗ Phục Uy, Phụ Công Thạch đã đi thuyết phục một thủ lĩnh nổi dậy khác là Miên Hải Triều (苗海潮) chịu nằm dưới quyền lãnh đạo của Đỗ Phục Uy. Sau đó, Phụ Công Thạch cũng góp sức trong cuộc tập kích một đội quân nổi dậy khác của thủ lĩnh Triệu Phá Trần (趙破陳).